package com.jiang.daily.Q2845;

import java.util.HashMap;
import java.util.List;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/04/26 0:11
 */
public class Solution {
    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        int n = nums.size();
        HashMap<Integer, Integer> cnt = new HashMap<>();
        long res = 0;
        int prefix = 0;
        cnt.put(0, 1);
        for (int i = 0; i < n; i++) {
            prefix += nums.get(i) % modulo == k ? 1 : 0;
            res += cnt.getOrDefault((prefix - k + modulo) % modulo, 0);
            cnt.put(prefix % modulo, cnt.getOrDefault(prefix % modulo, 0) + 1);
        }
        return res;
    }

    // 超时
//    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
//        List<int[]> list = new ArrayList<>(); // arr[0]表示当前key 满足nums[i] % modulo == k 的索引 i， arr[1]表示前一个key的索引，arr[2]表示后一个key的索引
//        int be = 0; // 表示前一个key的索引
//        int index = 0; // 表示list的索引
//        int i = 0, size = nums.size();
//        // 初始化list，确定第一个key的索引
//        for (; i < size; i++) {
//            if (nums.get(i) % modulo == k) {
//                list.add(new int[]{i, -1, size}); // 加入当前key，前一个key的索引为-1，后一个key的索引为size + 1
//                be = i; // 更新前一个key的索引
//                i++;
//                break;
//            }
//        }
//        // 遍历nums，确定所有key的索引
//        for (; i < size; i++) {
//            if (nums.get(i) % modulo == k) {
//                list.add(new int[]{i, be, size}); // 加入当前key，前一个key的索引为be，后一个key的索引为size + 1
//                list.get(index)[2] = i; // 更新前一个key的索引的后一个索引
//                be = i; // 更新前一个key的索引
//                index++;
//            }
//        }
//        long res = 0;
//        int len = list.size();
//        if (k == 0) {
//            // 当k为0时，需要特殊处理，nums[i] % modulo == 0
//            for (int i1 = 0; i1 < len; i1++) {
//                int t = list.get(i1)[0] - list.get(i1)[1] - 1;
//                res += (long) t * (t + 1) / 2;
//            }
//            int t = size - list.get(len - 1)[0] - 1;
//            res += (long) t * (t + 1) / 2;
//            k = modulo;
//        }
//        int l = 0, r = l + k - 1, n = 1; // {l r}表示滑动窗口的左右边界， n用于设置滑动窗口的大小
//
//        while (r < len) {
//            while (r < len) {
//                res += (long) (list.get(l)[0] - list.get(l)[1]) * (list.get(r)[2] - list.get(r)[0]); // list.get(l)[0] - list.get(l)[1] + 1表示从l的key到l前一个key之间有多少个数，list.get(r)[2] - list.get(r)[0]表示从r的key到r后一个key之间有多少个数
//                l++;
//                r++;
//            }
//
//            // 重新设置滑动窗口的大小
//            l = 0;
//            r = (l + k - 1) + (n * modulo);
//            n++;
//        }
//        return res;
//    }
}
